package primary.primary0;

public class S0005最长回文子串 {

    class Solution3 {
        /**
         * 73，看了答案的中心扩散法写的。回文子串太经典，要记一下。
         * 1. 注意一下奇偶数
         * 2. 这题O(n^2)解即可，动态规划做不出来，因为如果当前节点无法和上一个节点连起来的话，重新找当前节点结尾的最长回文串，这个很耗时
         */
        public String longestPalindrome(String s) {
            int maxLeft = 0;
            int maxRight = 0;
            for(int i = 0; i < s.length(); i++){
                loop1:
                for(int j = 0; i + j < s.length() && i - j >= 0; j++){
                    if(s.charAt(i + j) == s.charAt(i - j)){
                        if((2*j + 1) > maxRight - maxLeft){
                            // 这里直接记录结果，而不是记录首尾值，也差不多快
                            maxLeft = i - j;
                            maxRight = i + j + 1;
                        }
                    }else{
                        break loop1;
                    }
                }
                loop2:
                for(int j = 0; i + 1 + j < s.length() && i - j >= 0; j++){
                    if(s.charAt(i + 1 + j) == s.charAt(i - j)){
                        if((2*j + 2) > maxRight - maxLeft){
                            maxLeft = i - j;
                            maxRight = i + j + 2;
                        }
                    }else{
                        break loop2;
                    }
                }
            }
            return s.substring(maxLeft, maxRight);
        }
    }

    /**
     * 答案
     */
    public class Solution2 {

        public String longestPalindrome(String s) {
            int len = s.length();
            if (len < 2) {
                return s;
            }

            int maxLen = 1;
            int begin = 0;
            // dp[i][j] 表示 s[i..j] 是否是回文串
            boolean[][] dp = new boolean[len][len];
            // 初始化：所有长度为 1 的子串都是回文串
            for (int i = 0; i < len; i++) {
                dp[i][i] = true;
            }

            char[] charArray = s.toCharArray();
            // 递推开始
            // 先枚举子串长度
            for (int L = 2; L <= len; L++) {
                // 枚举左边界，左边界的上限设置可以宽松一些
                for (int i = 0; i < len; i++) {
                    // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                    int j = L + i - 1;
                    // 如果右边界越界，就可以退出当前循环
                    if (j >= len) {
                        break;
                    }

                    if (charArray[i] != charArray[j]) {
                        dp[i][j] = false;
                    } else {
                        if (j - i < 3) {
                            dp[i][j] = true;
                        } else {
                            dp[i][j] = dp[i + 1][j - 1];
                        }
                    }

                    // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                    if (dp[i][j] && j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        begin = i;
                    }
                }
            }
            return s.substring(begin, begin + maxLen);
        }
    }





    class Solution {
        public String longestPalindrome(String s) {
            if(s == null || s.length() <= 1){
                return s;
            }
            int curLen = 0;
            int preLen = 1;
            for(int i = 1; i < s.length(); i++){
                if(i - preLen - 1 > 0){
                    // 如果匹配不上的话，想要找当前值的回文子串，会很麻烦，要轮询，一产生轮询，就是O(n^2), 加上交叉就是三次方了
                }
            }
            return "";
        }
    }
}
